package com.lenl.datastruct.avltree;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-11 11:30
 * @description 平衡二叉树
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        //int[] arr={4,3,6,5,7,8};
        //int[] arr={10,12,8,9,7,6};
        //int[] arr={10,11,7,6,8,9};
        int[] arr={10,8,12,9,3,1};
        //创建AVLTree对象
        AVLTree avlTree=new AVLTree();
        //添加节点
        for (int i=0;i<arr.length;i++){
            avlTree.add(new Node(arr[i]));
        }
        //遍历
        System.out.println("中序遍历：");
        avlTree.infixOrder();

        System.out.println("未作平衡处理后：");
        System.out.println("树的高度："+avlTree.getRoot().height());
        System.out.println("左子树高度："+avlTree.getRoot().leftHeight());
        System.out.println("右子树高度："+avlTree.getRoot().rightHeight());


    }
}


//创建AVLTree
class AVLTree{
    private Node root;

    //获取根节点
    public Node getRoot(){
        return root;
    }

    //添加节点
    public void add(Node node){
        if(root==null){
            this.root=node;
        }else{
            root.add(node);
        }
    }
    //中序遍历
    public void infixOrder(){
        if(root!=null){
            root.infixOrder();
        }else{
            System.out.println("当前二叉排序树为空，不能遍历");
        }
    }
    //查找要删除的节点
    public Node search(int value){
        if(root==null){
            return null;
        }else{
            return  root.search(value);
        }
    }
    //查找父节点
    public Node searchParent(int value){
        if(root==null){
            return null;
        }else{
            return  root.searchParent(value);
        }
    }

    /**
     * 1.返回以node为根节点的二叉排序树的最小节点的值
     * 2.删除node为根节点的二叉排序树的最小节点
     *
     * @param node 传入的节点（当作二叉排序树的根节点）
     * @return 以node为根节点的二叉排序树的最小节点的值
     */
    public  int delRightTreeMin(Node node){
        Node taget=node;
        //循环查找左节点，皆会找到最小值
        while(taget.left!=null){
            taget=taget.left;
        }
        //这时target就指向了最小值
        //删除最小节点
        delNode(taget.value);
        return taget.value;

    }

    //删除节点
    public void delNode(int value){
        if(root ==null){
            return;
        }else{
            Node targetNode=search(value);
            //如果没有找到要删除的节点
            if(targetNode==null){
                return;
            }
            //如果当前二叉排序树只有一个节点
            if(root.left==null&&root.right==null){
                root=null;
                return;
            }

            //去找到targetNode的父节点
            Node parent=searchParent(value);
            //要考虑删除的是根节点的情况，此时parent为null


            //如果要删除的节点是叶子节点
            if(targetNode.left==null&&targetNode.right==null){
                //判断targetNode是父节点的左子节点还是右子节点
                if(parent.left!=null&&parent.left.value==value){
                    parent.left=null;
                }else if(parent.right!=null&&parent.right.value==value){
                    parent.right=null;
                }
            }else if(targetNode.left!=null&&targetNode.right!=null){
                //说明要删除的节点有左右两棵子树
                int minVal= delRightTreeMin(targetNode.right);
                targetNode.value=minVal;
            }else{
                //删除只有一棵子树地节点
                //如果要删除的节点有左子节点
                if(targetNode.left!=null){
                    //考虑没有父节点 这里视频中没有考虑到
                    if(parent==null){
                        targetNode.value=targetNode.left.value;
                        targetNode.left=targetNode.left.left;
                        targetNode.right=targetNode.left.right;
                    }else
                        //如果targetNode是parent的左子节点
                        if(parent.left.value==value){
                            parent.left=targetNode.left;
                        }else{
                            //说明targetNode是parent的右子节点
                            parent.right=targetNode.left;
                        }
                }else{
                    //考虑没有父节点 这里视频中没有考虑到
                    if(parent==null){
                        targetNode.value=targetNode.right.value;
                        targetNode.right=targetNode.right.right;
                        targetNode.left=targetNode.right.left;
                    }else

                        //要删除的节点有右子节点
                        //如果targetNode是parent的左子节点
                        if(parent.left.value==value){
                            parent.left=targetNode.right;
                        }else{
                            //说明targetNode是parent的右子节点
                            parent.right=targetNode.right;
                        }
                }
            }


        }
    }
}


//创建Node节点
class Node{
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value=value;
    }

    //返回左子树的高度
    public int leftHeight(){
        if(left==null){
            return 0;
        }
        return left.height();
    }
    //返回右子树的高度
    public int rightHeight(){
        if(right==null){
            return 0;
        }
        return right.height();
    }


    //返回当前节点的高度：以该节点为根节点的树的高度
    public int height(){
        return Math.max(left==null?0:left.height(),right==null?0: right.height())+1;
    }

    //添加节点的方法
    //递归的形式添加节点，需要满足二叉排序树的要求
    public void add(Node node){
        if(node==null){
            return;
        }
        //判断传入节点的值，和当前子树的根节点的关系
        if(node.value<this.value){
            if(this.left==null){
                //左子节点为空
                this.left=node;
            }else{
                this.left.add(node);
            }
        }else{
            if(this.right==null){
                this.right=node;
            }else{
                this.right.add(node);
            }
        }
        //添加完毕后，如果右子树的高度-左子树高度>1，左旋转
        if(this.rightHeight()-this.leftHeight()>1){
            //如果右子树的左子树大于右子树的右子树的高度，要先进行右旋转
            if(this.right!=null&& this.right.leftHeight()>this.right.rightHeight()){
                this.right.rightRotate();
            }
            this.leftRotate();
            return;
        }
        //如果左子树高度-右子树高度>1,右旋转
        if(this.leftHeight()-this.rightHeight()>1){
            //如果左子树的右子树高度大于左子树左子树高度，则先对左子树进行左旋转
            if(this.left !=null&&this.left.rightHeight()>this.left.leftHeight()){
                this.left.leftRotate();
            }
            this.rightRotate();
            return;
        }
    }

    //中序遍历
    public  void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }

    }
    //查找要删除的节点
    public Node search(int value){
        if(value==this.value){
            return this;
        }else if(value<this.value){
            //从左子树递归查找
            if(this.left!=null)
                return this.left.search(value);
            else
                return null;
        }else{
            if(this.right!=null)
                return this.right.search(value);
            else
                return null;
        }
    }
    //查找要删除节点的父节点
    public Node searchParent(int value){
        if((this.left!=null&&this.left.value==value)||(this.right!=null&&this.right.value==value)){
            return this;
        }else if(value <this.value&&this.left!=null){
            return this.left.searchParent(value);
        }else if(value>=this.value&&this.right!=null){
            return this.right.searchParent(value);
        }else{
            return null; //没有找到父节点
        }
    }

    //左旋转方法
    private void leftRotate(){
        //创建新节点，以当前根节点的值
        Node newNode=new Node(this.value);
        //把新的节点的左子树设置成当前节点的左子树
        newNode.left=this.left;
        //把新的节点的右子树设置成当前节点的右子树的左子树
        newNode.right=this.right.left;
        //把当前节点的值替换成右子节点的值
        this.value=this.right.value;
        //把当前节点的右子树设置成当前右子树的右子树
        this.right=this.right.right;
        //把当前节点的左子节点设置成新的节点
        this.left=newNode;
    }
    //右旋转方法
    private  void rightRotate(){
        Node newNode=new Node(this.value);
        //新节点的右子节点设置为当前节点的右子节点
        newNode.right=this.right;
        //新节点的左子节点指向当前节点左子节点的右子节点
        newNode.left=this.left.right;
        //当前节点的值改为左子节点的值
        this.value=this.left.value;
        //当前节点的左子节点改成当前节点左子节点的左子节点
        this.left=this.left.left;
        //当前节点的右子节点设置为新的节点
        this.right=newNode;

    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}